Find missing number

Time: O(N); Space: O(1); medium

Given an array containing N distinct numbers taken from 0, 1, 2, …, N, find the one that is missing from the array.

Example:

Input: [0, 1, 3]

Output: 2

Notes:

  • Your algorithm should run in linear runtime complexity.

  • Could you implement it using only constant extra space complexity?

[1]:

import operator
from functools import reduce

class Solution1(object):
    def missingNumber(self, nums) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        return reduce(operator.xor, nums,
                      reduce(operator.xor, range(len(nums) + 1)))

[2]:

s = Solution1()
assert s.missingNumber([0, 1, 3]) == 2

[3]:

class Solution2(object):
    def missingNumber(self, nums) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(range(len(nums)+1)) - sum(nums)

[4]:

s = Solution2()
assert s.missingNumber([0, 1, 3]) == 2